#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void AdjustDown(vector<int>& vi, int parent)
    {
        int child = parent * 2 + 1;
        while (child < vi.size())
        {
            if ((child + 1 < vi.size()) && (vi[child] < vi[child + 1]))
                child++;
            if (vi[parent] < vi[child])
                swap(vi[parent], vi[child]);
            else
                break;
            parent = child;
            child = 2 * parent + 1;
        }
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        vector<int> vi;
        if (cnt == 0) return vi;
        vi.resize(cnt);
        for (int i = 0; i < cnt; i++)
            vi[i] = stock[i];
        for (int i = (cnt - 2) / 2; i >= 0; i--)
        {
            AdjustDown(vi, i);
        }
        for (int i = cnt; i < stock.size(); i++)
        {
            if (stock[i] < vi[0])
            {
                vi[0] = stock[i];
                AdjustDown(vi, 0);
            }
        }
        return vi;
    }
};

class Solution {
public:
    void qsort(vector<int>& nums, int left, int right, int cnt)
    {
        if (left >= right) return;
        int key = left + rand() % (right - left + 1);
        swap(nums[key], nums[left]);
        int n = nums[left], begin = left, end = right;
        for (int i = left; i <= right;)
        {
            if (nums[i] < n) swap(nums[left++], nums[i++]);
            else if (nums[i] == n) i++;
            else swap(nums[right--], nums[i]);
        }
        if (left - begin > cnt) qsort(nums, begin, left - 1, cnt);
        else if (right + 1 - begin >= cnt) return;
        else qsort(nums, right + 1, end, cnt - right - 1 + begin);
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand((unsigned int)time(nullptr));
        qsort(stock, 0, stock.size() - 1, cnt);
        return vector<int>(stock.begin(), stock.begin() + cnt);
    }
};